package com.zhj.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 力扣509 斐波那契数列 0,1,1,2,3,5,8
 */
public class Test509 {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        // System.out.println(fibonacci(45));
        System.out.println(fibonacci2(45, new HashMap<>()));
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }

    private static int fibonacci(int n) {
        if (n < 2) {
            return n == 1 ? 1 : 0;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    }

    private static int fibonacci2(int n, Map<Integer,Integer> cache) {
        if (n < 2) {
            return n == 1 ? 1 : 0;
        }
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        int value = fibonacci2(n - 1, cache) + fibonacci2(n - 2, cache);
        cache.put(n,value);
        return value;
    }

    private static int fibonacci3(int n) {
        if (n < 2) {
            return n == 1 ? 1 : 0;
        }
        int a = 0;
        int b = 1;
        int temp = 0;
        for (int i = 2; i <= n; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }
}
